#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> ans;
        for (int i=0;i<=2 && i<=(int)s.size()-4;i++) {
            string sa=s.substr(0, i+1);
            int ia=stoi(sa);
            if (0<=ia && ia<=255 && (sa.size()==1 || sa[0]!='0'))
                for (int j=i+1;j<=i+3 && j<=(int)s.size()-3;j++) {
                    string sb=s.substr(i+1, j-i);
                    int ib=stoi(sb);
                    if (0<=ib && ib<=255 && (sb.size()==1 || sb[0]!='0'))
                        for (int k=j+1;k<=j+3 && k<=(int)s.size()-2;k++) {
                            string sc=s.substr(j+1, k-j);
                            int ic=stoi(sc);
                            if (0<=ic && ic<=255 && (sc.size()==1 || sc[0]!='0')) {
                                string sd=s.substr(k+1);
                                if (sd.size()>3) continue;
                                int id=stoi(sd);
                                if (0<=id && id<=255 && (sd.size()==1 || sd[0]!='0'))
                                    ans.push_back(sa+"."+sb+"."+sc+"."+sd);
                            }
                        }
                }
        }
        return ans;
    }
};
